/*
 * @lc app=leetcode.cn id=417 lang=cpp
 *
 * [417] 太平洋大西洋水流问题
 *
 * https://leetcode.cn/problems/pacific-atlantic-water-flow/description/
 *
 * algorithms
 * Medium (55.69%)
 * Likes:    517
 * Dislikes: 0
 * Total Accepted:    71K
 * Total Submissions: 127.5K
 * Testcase Example:  '[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]'
 *
 * 有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
 * 
 * 这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c)
 * 上单元格 高于海平面的高度 。
 * 
 * 岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
 * 
 * 返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动
 * 既可流向太平洋也可流向大西洋 。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 
 * 
 * 输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
 * 输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入: heights = [[2,1],[1,2]]
 * 输出: [[0,0],[0,1],[1,0],[1,1]]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * m == heights.length
 * n == heights[r].length
 * 1 <= m, n <= 200
 * 0 <= heights[r][c] <= 10^5
 * 
 * 
 */

// @lc code=start

static const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        _heights = heights;
        int m = _heights.size();
        int n = _heights[0].size();
        vector<vector<bool>> pacific(m, vector<bool>(n, false));       
        vector<vector<bool>> atlantic(m, vector<bool>(n, false));       

        for (int i = 0; i < m; ++i) {
            bfs(i, 0, pacific);
        }
        for (int j = 1; j < n; ++j) {
            bfs(0, j, pacific);
        }
        for (int i = 0; i < m; ++i) {
            bfs(i, n - 1, atlantic);
        }
        for (int j = 0; j < n - 1; ++j) {
            bfs(m - 1, j, atlantic);
        }

        vector<vector<int>> res;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pacific[i][j] && atlantic[i][j]) {
                    vector<int> tmp;
                    tmp.emplace_back(i);
                    tmp.emplace_back(j);
                    res.emplace_back(tmp);
                }
            }
        }

        return res;
    }

private:
    vector<vector<int>> _heights;

    void bfs(int row, int col, vector<vector<bool>>& ocean)
    {
        if (ocean[row][col]) {
            return ;
        }

        int m = _heights.size();
        int n = _heights[0].size();
        ocean[row][col] = true;
        queue<pair<int, int>> que;
        que.emplace(row, col);
        while (!que.empty()) {
            auto [r, c] = que.front();
            que.pop();
            for (int i = 0; i < 4; ++i) {
                int newRow = r + dirs[i][0];
                int newCol = c + dirs[i][1];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && _heights[newRow][newCol] >= _heights[r][c] && !ocean[newRow][newCol]) {
                    ocean[newRow][newCol] = true;
                    que.emplace(newRow, newCol);
                }
            }
        }
    }
};
// @lc code=end

